A major problem in the field of digital communications is that of decoding the signals received.
Indeed, after transmission, the signals are transported in a transmission channel that can be more or less noisy. The signals received are therefore more or less disrupted, and it may be necessary to implement a specific treatment in order to properly decode them.
To obtain good decoding performances, it is desirable to use an optimal maximum likelihood (ML) decoding technique. An optimal decoder makes it possible to estimate the likeliest candidate signal, given the observed signal received.
To perform an optimal ML decoding, all of the potential transmitted signals (also called candidate signals) are classically counted, and the likeliest signal is selected. For example, the selection criterion consists of calculating a Euclidean distance between the observed signal received and the candidate signals.
Unfortunately, such an exhaustive count is costly in terms of time and resources, and can be difficult to implement in real-time applications. Indeed, the number of candidates, and therefore the complexity of the decoder, exponentially increase with the length of the digital signal. For example, a digital signal having a length of 10 bits can have 210=1024 different values, and all of these values must be counted in the classic ML decoding.
To overcome this disadvantage of exhaustive enumerating, other decoding techniques have appeared, such as sequential decoding techniques. These techniques use a tree representation of the problem, in which each path from the root node to a leaf node is a potential transmitted signal.
Indeed, it is noted that a data structure can be represented in the form of a tree structure having a set of nodes. For a constellation 2n QAM (Quadrature Amplitude Modulation), n branches leave from a node of the tree. The first node of the tree is called the root node. Each node of a tree can have zero, one or more son nodes, which are located below it in the tree. A node that does not have any son node is called a leaf node. It corresponds to the lowest level in the tree. A node has at most one parent node, located above it in the tree. The root node is the highest node in the tree, and does not have a parent node. The depth (or dimension) of a node is the length of the path from said node to its root. The root node is the node on which operations on the tree ordinarily begin. All of the other nodes can be reached from it by following links.
From this tree representation, the sequential decoding counts a smaller number of candidate signals than in an optimal ML decoder. For example, with a number of symbols Q equal to 8 and by using a constellation 16 QAM, a classic ML decoder counts 168 candidate signals in order to decode a space/time code word, while a stack decoder counts only very few of them. To do this, the sequential decoding techniques take into account a cost (or metric) constraint, so as to determine a single candidate path inside a decoding tree. Classically, the cost associated with a current node is defined by the Euclidean distance between the signal received and the path between the root node and the current node.
The sequential decoding can be implemented in a stack decoder, delivering a hard estimation of the signal transmitted, i.e. a binary estimation, as described in particular in the documents “A fast sequential decoding algorithm using a stack” (F. Jelinek, “IBM Journal Research Development”, volume 13 pages 675 to 685, November 1969) or “A unified framework for tree search decoding: rediscovering the sequential decoder” (Arul Murugan et al., “IEEE transaction on information theory”, volume 52, pages 933 to 953, March 2006).
If no cost constraint is set, such a decoder has optimal ML performance. However, if a constraint is set, in order to limit the tree searching time, for example, the performances obtained are sub-optimal, i.e. inferior to the performances obtained by implementing an ML technique.
Such a sub-optimal decoding technique is therefore less complex and requires fewer resources than an optimal technique, but does not have good performance.
Sequential decoders delivering a soft estimation of the transmitted signal, i.e. a probabilistic estimation, as in the document “Soft-Input soft-output lattice sphere decoder for linear channels” (J. Boutros et al., IEEE Global Telecommunications Conference, 2003).
Unfortunately, these sequential soft decision decoders are very complex. Moreover, the list of potential paths determined from the decoding tree, and from which a probabilistic estimation of the transmitted signal is determined, is not optimized.